package threeSum;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @Date 2020/03/26
 * @author 王光浩
 * @Thinking 使用HashMap来完成（过于复杂更改写法）
 */
public class MyMethodOne {
	public List<List<Integer>> threeSum(int[] nums) {
		HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
		List<List<Integer>> ret=new LinkedList<List<Integer>>();
		//将所有元素加入到HashMap中,并且统计次数
		for(int tem:nums)
			map.put(tem, map.getOrDefault(tem, 0)+1);
		//遍历HashMap，来获取所有可能元组
		for(Map.Entry<Integer, Integer> tem:map.entrySet()) {
			if(tem.getValue()>=3) {
				if(tem.getKey()*3==0) {
					List<Integer> list=new LinkedList<Integer>();
					list.add(tem.getValue());
					list.add(tem.getValue());
					list.add(tem.getValue());
					ret.add(list);
				}
			}
			if(tem.getValue()>=2) {
				if(map.containsKey(-2*tem.getKey()) && map.get(-2*tem.getKey())>0 && -2*tem.getKey()!=0) {
					List<Integer> list=new LinkedList<Integer>();
					list.add(tem.getKey());
					list.add(tem.getKey());
					list.add(-2*tem.getKey());
					ret.add(list);
				}
			}
			map.put(tem.getKey(), 0);
			for(Map.Entry<Integer, Integer> next:map.entrySet()) {
				if(next.getValue()<=0)continue;  //排除所以已经遍历过的元素
				int key=-next.getKey()-tem.getKey();
				if(map.containsKey(key)) {
					if(map.get(key)<=0)break; //最后一个元素必须是没有遍历过的元素
					if(key==next.getKey()) { //如果最后一个元素与第二个元素同值
						if(map.get(key)<2)break;
					}
					List<Integer> list=new LinkedList<Integer>();
					list.add(tem.getKey());
					list.add(next.getKey());
					list.add(key);
					ret.add(list);
					break;
				}
				
			}
		}
		return ret;
    }
}
